class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(auto x:nums)sum+=x;
        if(sum%2!=0)return false;
        int ret=sum>>1;
        int dp[ret+1];
        memset(dp,0,sizeof dp);
        for(auto w:nums)
        {
            int v=w;
            for(int j=ret;j>=v;j--)
            {
                dp[j]=max(dp[j],dp[j-v]+w);
            }
        }
        if(dp[ret]==ret)return true;
        return false;
    }
};

